//给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
//
//
//
//
//
//
// 示例 1：
//
//
//输入：nums = [-4,-1,0,3,10]
//输出：[0,1,9,16,100]
//解释：平方后，数组变为 [16,1,0,9,100]
//排序后，数组变为 [0,1,9,16,100]
//
// 示例 2：
//
//
//输入：nums = [-7,-3,2,3,11]
//输出：[4,9,9,49,121]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -10⁴ <= nums[i] <= 10⁴
// nums 已按 非递减顺序 排序
//
//
//
//
// 进阶：
//
//
// 请你设计时间复杂度为 O(n) 的算法解决本问题
//
//
// Related Topics 数组 双指针 排序 👍 912 👎 0


package leetcode.editor.cn;

/**
 * 有序数组的平方
 * @author CodeTheory
 * @date 2023-11-05 00:42:18
 */
public class P977_SquaresOfASortedArray{
	 public static void main(String[] args) {
	 	 Solution solution = new P977_SquaresOfASortedArray().new Solution();
//		 int[] ints = solution.sortedSquares(new int[]{-4, -1, 0, 3, 10});
		 int[] ints = solution.sortedSquares(new int[]{-4, -1, 0, 3, 10});
		 for (int i : ints) {
			 System.out.println(i);
		 }
	 }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortedSquares(int[] nums) {
		int left = 0, right = nums.length - 1, index = right;
		int[] newNums = new int[nums.length];
		while (left <= right) {
			if (abs(nums[left]) > abs(nums[right])) {
				newNums[index--] = nums[left] * nums[left++];
			} else {
				newNums[index--] = nums[right] * nums[right--];
			}
		}
		return newNums;
    }

	private int abs(int num) {
		return num > 0 ? num : -num;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
